\subsection{Lower bounds for Zarankiewicz numbers}
Recall the Zarankiewicz numbers \( Z(n,t) \), the maximum number of edges between a bipartite graph on \( (n, n) \) vertices, before a \( K_{t,t} \) is forced.
We have shown that \( Z(n,t) \leq 2n^{2 - \frac 1t} \), but we have found no lower bound.
\begin{theorem}
	Let \( t \geq 2 \).
	Then \( Z(n,t) \geq \frac{1}{2} n^{2 - \frac{2}{t+1}} \).
\end{theorem}
\begin{proof}[Proof excluding the \( t + 1 \) term]
	Suppose we include each edge in the graph with probability \( p \).
	Let \( Z \) be a random variable that counts the number of \( K_{t,t} \) in the bipartite graph \( G \) on \( (n, n) \) vertices.
	Then
	\[ Z = \sum_{A \in X^{(t)}, B \in Y^{(t)}} \symbb 1(\text{all edges between \( A \) and \( B \) lie in \( G \)}) \]
	We find
	\[ \expect Z = \sum_{A \in X^{(t)}, B \in Y^{(t)}} \prob{\text{all edges between \( A \) and \( B \) lie in \( G \)}} = {\binom n t}^2 p^{t^2} \leq \frac{n^{2t}}{4} p^{t^2} = \frac{1}{4} (n^2 p^t)^t \]
	So if \( p = n^{-\frac{2}{t}} \), then our upper bound is at most \( \frac{1}{4} \).
	Then \( \prob{X \geq 1} \leq \frac{1}{4} \) by Markov's inequality.
	Note that \( \expect{e(G)} = pa^2 = n^{2 - \frac 2 t} \).
	So \( \prob{e(G) \leq \frac{pn^2}{2}} \leq \frac{1}{2} \).
	So with probability greater than \( \frac 14 \), we have \( e(G) > \frac{1}{2} pn^2 = \frac{1}{2} n^{2 - \frac{2}{t}} \) and \( G \) does not contain a \( K_{t,t} \).
\end{proof}
\begin{proof}
	Let \( G = (X \sqcup Y, E) \) be a random bipartite graph with \( \abs{X} = \abs{Y} = n \), such that \( xy \in E \) with probability \( p = n^{-\frac{2}{t+1}} \).
	Let \( \widetilde G \) be the graph \( G \) with an edge removed from each \( K_{t,t} \).
	By definition, \( \widetilde G \) has no \( K_{t,t} \).
	Note that \( e(\widetilde G) \geq e(G) - (\text{amount of } K_{t,t} \text{ in } G) \).
	Taking expectations, \( \expect{e(\widetilde G)} \geq \expect{e(G)} - \expect{\text{amount of } K_{t,t}} \).
	We have \( \expect{e(G)} = pn^2 \), and the expected amount of \( K_{t,t} \) subgraphs of \( G \) is \( {\binom n t}^2 p^{t^2} \).
	Substituting in for \( p \) and approximating,
	\[ \expect{e(\widetilde G)} \geq n^{2-\frac{2}{t+1}} - \frac{n^{2t}}{2} p^{t^2} \]
	Note that
	\[ n^{2t} p^{t^2} = (n^2 p^t)^t = (n^2 n^{\frac{-2t}{t+1}})^t = (n^{\frac{2(t+1) - 2t}{t+1}})^t = n^{\frac{2t}{t+1}} = n^{2 - \frac{2}{t+1}} \]
	Hence
	\[ \expect{e(\widetilde G)} \geq \frac{1}{2} n^{2 - \frac{2}{t+1}} \]
	So there must exist a graph \( \widetilde G \) with no \( K_{t,t} \) and that has at least \( \frac{1}{2} n^{2 - \frac{2}{t+1}} \) edges.
\end{proof}

\subsection{Girth}
\begin{definition}
	The \emph{girth} of a graph is the length of the shortest cycle.
\end{definition}
\begin{proposition}[Markov]
	Let \( X \) be a nonnegative random variable.
	Then for all \( t > 0 \),
	\[ \prob{X \geq t} \leq \frac{\expect{X}}{t} \]
\end{proposition}
\begin{proposition}
	Let \( G \) be a graph.
	Then \( \chi(G) \geq \frac{\abs{G}}{\alpha(G)} \), where \( \alpha(G) \) is the size of the largest independent set (non-adjacent vertices) in \( G \).
\end{proposition}
\begin{proof}
	Let \( c \) be a colouring of \( G \) with \( k = \chi(G) \) colours.
	Let \( C_i \) be the set of vertices coloured \( i \).
	Then the \( C_i \) are each independent sets.
	We have \( \abs{G} = \abs{C_1} + \dots + \abs{C_k} \leq k\alpha(G) = \chi(G)\alpha(G) \).
\end{proof}
\begin{theorem}[Erd\H{o}s]
	For all \( k, g \geq 3 \), there exists a graph \( G \) with \( \chi(G) \geq k \) and girth at least \( g \).
\end{theorem}
\begin{proof}
	Let \( G \) be a random graph on \( \qty{1, \dots, n} \) where each edge \( ij \) is included with probability \( p = n^{-1 + \frac{1}{g}} \).
	Let \( X_i \) be the random variable that counts the number of cycles in \( G \) of length \( i \).
	Let \( X = X_3 + \dots + X_{g-1} \).
	Now, note that \( \prob{X \geq \frac{n}{2}} \leq \frac{2}{n} \expect{X} \).
	\begin{align*}
		\expect{X} &= \sum_{i=3}^{g-1} \expect{X_i} \\
		&\leq \sum_{i=3}^{g-1} \frac{n(n-1) \dots (n-i+1)}{i} p^i \\
		&\leq \sum_{i=3}^{g-1} (np)^i \\
		&= \sum_{i=3}^{g-1} n^{\frac{i}{g}} \\
		&\leq c n^{-\frac{1}{g}} < \frac{1}{2}
	\end{align*}
	for a constant \( c \).
	Now, let \( Y \) be the random variable counting the number of independent sets of \( s = \frac{n}{2k} \) vertices (up to rounding).

	\begin{align*}
		\prob{Y \geq 1} &\leq \expect{Y} \\
		&= \binom n s (1-p)^{\binom s 2} \\
		&\leq n^s e^{-p\binom s 2} \\
		&= \qty(n^2 e^{-p(s-1)})^{\frac{s}{2}} \\
		&\leq \qty(2n^2 e^{-\frac{n^{\frac 1 g}}{2k}})^{\frac{s}{2}} \\
		&< \frac{1}{2}
	\end{align*}
	for \( n \) sufficiently large.
	We have shown that \( G \) has at most \( \frac{n}{2} \) cycles of length at most \( g - 1 \) with probability at least \( \frac{1}{2} \), and \( G \) has \( \alpha(G) \leq \frac{n}{2k} \) with probability at least \( \frac{1}{2} \).
	Hence there is a graph \( G \) with both properties.
	Let \( \widetilde G \) be \( G \) with a vertex deleted from each cycle of length less than \( g \).
	Then \( \widetilde G \) has girth at least \( g \).
	Further,
	\[ \chi(\widetilde G) \geq \frac{\abs{\widetilde G}}{\alpha(\widetilde G)} \geq \frac{\frac{n}{2}}{\alpha(G)} \geq \frac{\frac{n}{2}}{\frac{n}{2k}} = k \]
	as required.
\end{proof}

\subsection{Binomial random graphs}
\begin{definition}
	The \emph{binomial random graph} on \( n \) vertices with parameter \( p \in [0,1] \) is the probability space \( G(n,p) \) on the graphs on \( n \) vertices, where each potential edge is included in the graph independently with probability \( p \).
\end{definition}
Let \( (a_n), (b_n) \) be sequences of nonnegative numbers, and \( b_n \neq 0 \) for sufficiently large \( n \).
Then we write \( a_n \ll b_n \) if \( \lim_{n \to \infty} \frac{a_n}{b_n} = 0 \).
Let \( X \) be the random variable that counts the number of triangles \( K_3 \) in some random graph \( G \sim G(n,p) \).
Then \( \expect{X} = \binom n 3 p^3 \).

Note that if \( p \ll \frac{1}{n} \), so \( pn \to 0 \), we have \( \expect{X} \leq n^3 p^3 \to 0 \).
By Markov's inequality, \( \prob{K_3 \subset G} = \prob{X \geq 1} \leq \expect{X} \to 0 \).

If \( p \gg \frac{1}{n} \), so \( pn \to \infty \), then we have \( \expect{X} \geq \frac{(n - 3)^3}{6} p^3 \to \infty \).
So asymptotically we have infinitely many triangles.
We can also show that \( \prob{X \geq 1} \to 1 \), but this does not follow immediately from the previous result.
\begin{proposition}[Chebyshev]
	Let \( X \) be a random variable, and let \( t > 0 \).
	Then
	\[ \prob{\abs{X - \expect{X}} \geq t} \leq \frac{\Var X}{t^2} \]
\end{proposition}
\begin{proposition}[second moment method]
	Let \( X \) be a random variable taking values in \( \mathbb N \).
	Then
	\[ \prob{X = 0} \leq \frac{\Var X}{(\expect{X})^2} \]
\end{proposition}
\begin{proof}
	\[ \prob{X = 0} \leq \prob{\abs{X - \expect{X}} \geq \expect{X}} \leq \frac{\Var X}{(\expect{X})^2} \]
\end{proof}
\begin{theorem}
	Let \( G \sim G(n,p) \) be a binomial random graph.
	Then
	\[ \lim_{n \to \infty} \prob{K_3 \subset G} = \begin{cases}
		0 & p \ll \frac{1}{n} \\
		1 & p \gg \frac{1}{n}
	\end{cases} \]
\end{theorem}
\begin{proof}
	Let \( X \) be the random variable counting the triangles in \( G \).
	If \( p \ll \frac{1}{n} \), then \( \expect{X} \to 0 \) so \( \prob{X \geq 1} \to 0 \).
	Now suppose \( p \gg \frac{1}{n} \).
	Let \( p \gg \frac{1}{n} \).
	Now, \( \prob{X = 0} \leq \frac{\Var X}{(\expect{X})^2} \).
	So it suffices to show that \( \frac{\Var X}{(\expect{X})^2} \to 0 \).
	We have
	\begin{align*}
		X &= \sum_{K \in \qty{0, \dots, n}^{(3)}} \symbb 1(K \text{ is a triangle in } G) \\
		X^2 &= \sum_{K \in \qty{0, \dots, n}^{(3)}} \sum_{L \in \qty{0, \dots, n}^{(3)}} \symbb 1(K, L \text{ are triangles in } G) \\
		\expect{X^2} &= \sum_{K \in \qty{0, \dots, n}^{(3)}} \sum_{L \in \qty{0, \dots, n}^{(3)}} \prob{K, L \text{ are triangles in } G}
	\end{align*}
	and
	\[ (\expect{X})^2 = \sum_{K \in \qty{0, \dots, n}^{(3)}} \sum_{L \in \qty{0, \dots, n}^{(3)}} \prob{K \text{ is a triangle in } G} \prob{L \text{ is a triangle in } G} \]
	When computing \( \expect{X^2} - (\expect{X})^2 \), the only terms that do not cancel are those terms which share edges.
	\begin{align*}
		\expect{X^2} - (\expect{X})^2 &\leq \sum_{K \in \qty{0, \dots, n}^{(3)}} \sum_{L \text{ that shares a single edge with } K} \prob{K, L \text{ are triangles in } G} \\
		&+ \sum_{K \in \qty{0, \dots, n}^{(3)}} \prob{K \text{ is a triangle in } G} \\
		&\leq \sum_{K \in \qty{0, \dots, n}^{(3)}} \sum_{L \text{ that shares a single edge with } K} \prob{K, L \text{ are triangles in } G} + \expect{X} \\
		&\leq \underbrace{n^4 p^5}_{\mathclap{four vertices, five edges}} + \expect{X}
	\end{align*}
	Hence,
	\[ \frac{\Var X}{(\expect{X})^2} \leq \frac{n^4 p^5 + \expect{X}}{(\expect{X})^2} \leq X \frac{n^4 p^5}{(p^3 n^3)^2} + \frac{1}{\expect{X}} \leq \frac{1}{pn^2} + \frac{1}{\expect{X}} \to 0 \]
\end{proof}
\begin{remark}
	We see a `phase transition' from in \( \prob{K_3 \subset G} \) as \( p \) moves from below \( \frac{1}{n} \) to above \( \frac{1}{n} \).
	Suppose \( p = \frac{\lambda}{n} \) for some fixed \( \lambda > 0 \).
	Here, \( \lim_{n \to \infty} \prob{K_3 \subset G} = 1 - e^{-\frac{\lambda^3}{6}} \), but this result will not be proven.
\end{remark}
\begin{remark}
	We have seen that if the expected number of triangles increases to infinity, then the probability that \( G \sim G(n,p) \) contains a triangle converges to 1.
	However, this is not true in general, replacing `triangle' with another graph.
	Consider the graph \( H \) defined by a triangle with 1000 extra disjoint vertices.
	Here, the expected amount of copies of \( H \) is \( \binom{n}{1003} p^3 \approx \frac{n^{1003}}{1003!} p^3 \), which becomes large when \( p = n^{-\frac{1003}{3}} < \frac{1}{n} \).
	If \( K \) is the `densest' subgraph of \( H \), then if the expected amount of copies of \( K \) tends to infinity, the probability that \( G \) contains a copy of \( H \) tends to 1.
\end{remark}

\subsection{Connectedness}
Throughout this section, we will use the inequality \( 1 - x \leq e^{-x} \).
\begin{proposition}
	Let \( G \sim G(n,p) \).
	Then, for all \( \varepsilon > 0 \), we have
	\[ \lim_{n \to \infty} \prob{G \text{ has an isolated vertex}} = \begin{cases}
		0 & p \geq (1 + \varepsilon) \frac{\log n}{n} \\
		1 & p \leq (1 - \varepsilon) \frac{\log n}{n}
	\end{cases} \]
	where a vertex is \emph{isolated} if its degree is zero.
\end{proposition}
\begin{proof}
	Let \( I \) be the number of isolated vertices in \( G \).
	Then,
	\[ \expect{I} = \sum_{i=1}^n \prob{v_i \text{ is isolated}} = \sum_{i=1}^n (1-p)^{n-1} = n(1-p)^{n-1} \]
	If \( p \geq (1 + \varepsilon) \frac{\log n}{n} \), then
	% TODO: correction for first inequality
	\[ \expect{I} = \frac{n(1-p)^n}{1-p} \leq ne^{-pn} \leq n e^{-(1+\varepsilon) \frac{\log n}{n} n} = ne^{-(1+\varepsilon) \log n} = n n^{-(1 + \varepsilon)} = n^{-\varepsilon} \to 0 \]
	Hence, by Markov's inequality, the probability that \( G \) has an isolated vertex is \( \prob{I \geq 1} \leq \expect{I} \to 0 \).
	If \( p \leq (1 - \varepsilon) \frac{\log n}{n} \), then
	\[ \expect{I} = \frac{n(1-p)^n}{1-p} \geq n(1-p)^n \geq ne^{-\qty(1 + \frac{\varepsilon}{4}) pn} \]
	for sufficiently large \( n \), and sufficiently small \( \varepsilon \).
	This statement holds because \( 1-p = e^{\log(1-p)} \) and Taylor's theorem implies \( \log (1-p) = -p + \frac{p^2}{2} + o(p^2) \).
	Then
	\[ \expect{I} \geq ne^{-\qty(1 + \frac{\varepsilon}{4})(1-\varepsilon)\log n} = nn^{-\qty(1 + \frac{\varepsilon}{4})(1-\varepsilon)} = nn^{-1 + \frac{3\varepsilon}{4} + \frac{\varepsilon^2}{4}} = n^{\frac{3\varepsilon}{4} + \frac{\varepsilon^2}{4}} \to \infty \]
	We will apply the second moment method on \( I \).
	We have \( \prob{I = 0} \leq \frac{\Var I}{(\expect I)^2} \).
	\begin{align*}
		\Var I &= \expect{I^2} - (\expect{I})^2 \\
		&= \sum_{u, v \in V(G)} \prob{d(u) = 0, d(v) = 0} - \sum_{u,v \in V(G)} \prob{d(u) = 0} \prob{d(v) = 0} \\
		&\leq \expect{I} + \sum_{u \neq v} \qty( \prob{d(u) = 0, d(v) = 0} - \prob{d(u) = 0}\prob{d(v) = 0} ) \\
		&= \expect{I} + \sum_{u \neq v} \qty((1-p)^{2(n-1)} - (1-p)^{2(n-1)}) \\
		&\leq \expect{I} + n^2 (1-p)^{2(n-1)} \qty(\frac{1}{1-p} - 1) \\
		\frac{\Var I}{(\expect{I})^2} &\leq \frac{1}{\expect{I}} \frac{1}{n^2 (1-p)^{2(n-1)}} n^2 (1-p)^{2(n-1)} \qty(\frac{1}{1-p} - 1) \\
		&\leq \frac{1}{\expect{I}} + \frac{1}{1-p} - 1 \to 0
	\end{align*}
	since \( p \to 0 \) and \( \expect I \to \infty \) for \( p < (1 - \varepsilon) \frac{\log n}{n} \), as required.
\end{proof}
\begin{theorem}
	Let \( G \sim G(n,p) \).
	Then for all \( \varepsilon > 0 \), we have
	\[ \lim_{n \to \infty} \prob{G \text{ connected}} = \begin{cases}
		1 & p \geq (1 + \varepsilon) \frac{\log n}{n} \\
		0 & p \leq (1 - \varepsilon) \frac{\log n}{n}
	\end{cases} \]
\end{theorem}
\begin{remark}
	This is an example of a \emph{sharp threshold}.
	Above, we saw the \emph{coarse threshold} \( p \gg \frac 1 n \) and \( p \ll \frac 1 n \).
	Often, sharp thresholds are seen in relation to global properties, and coarse thresholds are seen when analysing local properties.
\end{remark}
\begin{proof}
	Suppose \( p \leq (1-\varepsilon) \frac{\log n}{n} \).
	We want to show that \( \lim_{n \to \infty} \prob{G \text{ connected}} \) converges to zero.
	This follows from the fact that \( \prob{G \text{ connected}} \geq \prob{G \text{ has no isolated vertex}} \to 0 \).

	Now suppose \( p \geq (1 + \varepsilon) \frac{\log n}{n} \).
	We now want to show that \( \lim_{n \to \infty} \prob{G \text{ connected}} \) converges to one.
	If \( G \) is not connected, we can find \( A \subset V(G) \) where \( 1 \leq \abs{A} \leq \frac{n}{2} \), and there are no edges between \( A \) and \( V(G) \setminus A \).
	Consider

	\begin{align*}
		\prob{G \text{ not connected}} &= \prob{\exists A \subset V(G),\, 0 < \abs{A} \leq \frac{n}{2}, e(A, V(G) \setminus A) = 0} \\
		&= \prob{\bigcup_{A \subset V(G), 0 < \abs{A} \leq \frac{n}{2}} \qty{e(A, V(G) \setminus A) = 0}} \\
		&\leq \sum_{A \subset V(G),\, 0 < \abs{A} \leq \frac{n}{2}} \prob{e(A, V(G) \setminus A) = 0} \\
		&= \sum_{A \subset V(G),\, 0 < \abs{A} \leq \frac{n}{2}} (1-p)^{\abs{A}(n-\abs{A})} \\
		&= \sum_{k=1}^{\floor*{\frac{n}{2}}} \binom{n}{k} (1-p)^{k (n-k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} \binom n k (1-p)^{k (n-k)} + \sum_{k=\frac{\varepsilon n}{4}} \binom n k (1-p)^{k (n - k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} n^k e^{-pk(n-k)} + \sum_{k=\frac{\varepsilon n}{4}} \binom n k (1-p)^{k (n - k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} \qty(ne^{-(1+\varepsilon) \frac{\log n}{n} (n-k)})^k + \sum_{k=\frac{\varepsilon n}{4}} \binom n k (1-p)^{k (n - k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} \qty(ne^{-(1+\varepsilon) \frac{\log n}{n} n\qty(1 - \frac{\varepsilon}{4})})^k + \sum_{k=\frac{\varepsilon n}{4}} \binom n k (1-p)^{k (n - k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} \qty(ne^{-(1+\varepsilon) \log n \qty(1 - \frac{\varepsilon}{4})})^k + \sum_{k=\frac{\varepsilon n}{4}} \binom n k (1-p)^{k (n - k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} \qty(ne^{-\log n\qty(1+\frac{3\varepsilon}{4})})^k + \sum_{k=\frac{\varepsilon n}{4}} \binom n k (1-p)^{k (n - k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} \underbrace{\qty(n^{-\qty(1+\frac{3\varepsilon}{4})})^k}_{\to 0} + \sum_{k=\frac{\varepsilon n}{4}} \binom n k (1-p)^{k (n - k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} \qty(n^{-\qty(1+\frac{3\varepsilon}{4})})^k + \sum_{k=\frac{\varepsilon n}{4}} 2^n e^{-(1 + \varepsilon) \frac{\log n}{n} k(n-k)} \\
		&\leq \sum_{k=1}^{\frac{\varepsilon n}{4}} \qty(n^{-\qty(1+\frac{3\varepsilon}{4})})^k + \sum_{k=\frac{\varepsilon n}{4}} \underbrace{2^n e^{-(1 + \varepsilon) \frac{\log n}{n} \frac{\varepsilon n}{4} \frac{n}{2}}}_{\to 0}
	\end{align*}
	as required.
\end{proof}
